#ifndef __RBTREE_H__
#define __RBTREE_H__

#include <stdio.h>
#include <stdlib.h>

#define RED 1
#define BLACK 2

#define ENABLE_KEY_CHAR 1
#if ENABLE_KEY_CHAR
typedef char *KEY_TYPE;
#else
typedef int KEY_TYPE;
#endif

typedef struct _rbtree_node
{
    unsigned char color;
    struct _rbtree_node *right;
    struct _rbtree_node *left;
    struct _rbtree_node *parent;

    KEY_TYPE key;
    void *value;
} rbtree_node;

typedef struct _rbtree
{
    rbtree_node *root;
    rbtree_node *nil;

    int count;
} rbtree;

rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x);
rbtree_node *rbtree_maxi(rbtree *T, rbtree_node *x);
rbtree_node *rbtree_successor(rbtree *T, rbtree_node *x);
void rbtree_left_rotate(rbtree *T, rbtree_node *x);
void rbtree_right_rotate(rbtree *T, rbtree_node *y);
void rbtree_insert_fixup(rbtree *T, rbtree_node *z);
void rbtree_insert(rbtree *T, rbtree_node *z);
void rbtree_delete_fixup(rbtree *T, rbtree_node *x);
rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z);
rbtree_node *rbtree_search(rbtree *T, KEY_TYPE key);
void rbtree_traversal(rbtree *T, rbtree_node *node);

#endif